#include <taiju/const-bit-vector.h>

namespace taiju {

const UInt8 ConstBitVector::table_[9][256] = {
	{
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
	},
	{
		1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5,
		1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6,
		1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5,
		1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 7,
		1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5,
		1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6,
		1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5,
		1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 8,
		1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5,
		1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6,
		1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5,
		1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 7,
		1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5,
		1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6,
		1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5,
		1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 8
	},
	{
		2, 3, 3, 4, 2, 4, 4, 5, 2, 3, 3, 5, 2, 5, 5, 6,
		2, 3, 3, 4, 2, 4, 4, 6, 2, 3, 3, 6, 2, 6, 6, 7,
		2, 3, 3, 4, 2, 4, 4, 5, 2, 3, 3, 5, 2, 5, 5, 7,
		2, 3, 3, 4, 2, 4, 4, 7, 2, 3, 3, 7, 2, 7, 7, 8,
		2, 3, 3, 4, 2, 4, 4, 5, 2, 3, 3, 5, 2, 5, 5, 6,
		2, 3, 3, 4, 2, 4, 4, 6, 2, 3, 3, 6, 2, 6, 6, 8,
		2, 3, 3, 4, 2, 4, 4, 5, 2, 3, 3, 5, 2, 5, 5, 8,
		2, 3, 3, 4, 2, 4, 4, 8, 2, 3, 3, 8, 2, 8, 8, 8,
		2, 3, 3, 4, 2, 4, 4, 5, 2, 3, 3, 5, 2, 5, 5, 6,
		2, 3, 3, 4, 2, 4, 4, 6, 2, 3, 3, 6, 2, 6, 6, 7,
		2, 3, 3, 4, 2, 4, 4, 5, 2, 3, 3, 5, 2, 5, 5, 7,
		2, 3, 3, 4, 2, 4, 4, 7, 2, 3, 3, 7, 2, 7, 7, 8,
		2, 3, 3, 4, 2, 4, 4, 5, 2, 3, 3, 5, 2, 5, 5, 6,
		2, 3, 3, 4, 2, 4, 4, 6, 2, 3, 3, 6, 2, 6, 6, 8,
		2, 3, 3, 4, 2, 4, 4, 5, 2, 3, 3, 5, 2, 5, 5, 8,
		2, 3, 3, 4, 2, 4, 4, 8, 2, 3, 3, 8, 2, 8, 8, 8
	},
	{
		3, 4, 4, 5, 4, 5, 5, 6, 3, 5, 5, 6, 5, 6, 6, 7,
		3, 4, 4, 6, 4, 6, 6, 7, 3, 6, 6, 7, 6, 7, 7, 8,
		3, 4, 4, 5, 4, 5, 5, 7, 3, 5, 5, 7, 5, 7, 7, 8,
		3, 4, 4, 7, 4, 7, 7, 8, 3, 7, 7, 8, 7, 8, 8, 8,
		3, 4, 4, 5, 4, 5, 5, 6, 3, 5, 5, 6, 5, 6, 6, 8,
		3, 4, 4, 6, 4, 6, 6, 8, 3, 6, 6, 8, 6, 8, 8, 8,
		3, 4, 4, 5, 4, 5, 5, 8, 3, 5, 5, 8, 5, 8, 8, 8,
		3, 4, 4, 8, 4, 8, 8, 8, 3, 8, 8, 8, 8, 8, 8, 8,
		3, 4, 4, 5, 4, 5, 5, 6, 3, 5, 5, 6, 5, 6, 6, 7,
		3, 4, 4, 6, 4, 6, 6, 7, 3, 6, 6, 7, 6, 7, 7, 8,
		3, 4, 4, 5, 4, 5, 5, 7, 3, 5, 5, 7, 5, 7, 7, 8,
		3, 4, 4, 7, 4, 7, 7, 8, 3, 7, 7, 8, 7, 8, 8, 8,
		3, 4, 4, 5, 4, 5, 5, 6, 3, 5, 5, 6, 5, 6, 6, 8,
		3, 4, 4, 6, 4, 6, 6, 8, 3, 6, 6, 8, 6, 8, 8, 8,
		3, 4, 4, 5, 4, 5, 5, 8, 3, 5, 5, 8, 5, 8, 8, 8,
		3, 4, 4, 8, 4, 8, 8, 8, 3, 8, 8, 8, 8, 8, 8, 8
	},
	{
		4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
		4, 6, 6, 7, 6, 7, 7, 8, 6, 7, 7, 8, 7, 8, 8, 8,
		4, 5, 5, 7, 5, 7, 7, 8, 5, 7, 7, 8, 7, 8, 8, 8,
		4, 7, 7, 8, 7, 8, 8, 8, 7, 8, 8, 8, 8, 8, 8, 8,
		4, 5, 5, 6, 5, 6, 6, 8, 5, 6, 6, 8, 6, 8, 8, 8,
		4, 6, 6, 8, 6, 8, 8, 8, 6, 8, 8, 8, 8, 8, 8, 8,
		4, 5, 5, 8, 5, 8, 8, 8, 5, 8, 8, 8, 8, 8, 8, 8,
		4, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
		4, 6, 6, 7, 6, 7, 7, 8, 6, 7, 7, 8, 7, 8, 8, 8,
		4, 5, 5, 7, 5, 7, 7, 8, 5, 7, 7, 8, 7, 8, 8, 8,
		4, 7, 7, 8, 7, 8, 8, 8, 7, 8, 8, 8, 8, 8, 8, 8,
		4, 5, 5, 6, 5, 6, 6, 8, 5, 6, 6, 8, 6, 8, 8, 8,
		4, 6, 6, 8, 6, 8, 8, 8, 6, 8, 8, 8, 8, 8, 8, 8,
		4, 5, 5, 8, 5, 8, 8, 8, 5, 8, 8, 8, 8, 8, 8, 8,
		4, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8
	},
	{
		5, 6, 6, 7, 6, 7, 7, 8, 6, 7, 7, 8, 7, 8, 8, 8,
		6, 7, 7, 8, 7, 8, 8, 8, 7, 8, 8, 8, 8, 8, 8, 8,
		5, 7, 7, 8, 7, 8, 8, 8, 7, 8, 8, 8, 8, 8, 8, 8,
		7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		5, 6, 6, 8, 6, 8, 8, 8, 6, 8, 8, 8, 8, 8, 8, 8,
		6, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		5, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		5, 6, 6, 7, 6, 7, 7, 8, 6, 7, 7, 8, 7, 8, 8, 8,
		6, 7, 7, 8, 7, 8, 8, 8, 7, 8, 8, 8, 8, 8, 8, 8,
		5, 7, 7, 8, 7, 8, 8, 8, 7, 8, 8, 8, 8, 8, 8, 8,
		7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		5, 6, 6, 8, 6, 8, 8, 8, 6, 8, 8, 8, 8, 8, 8, 8,
		6, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		5, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8
	},
	{
		6, 7, 7, 8, 7, 8, 8, 8, 7, 8, 8, 8, 8, 8, 8, 8,
		7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		6, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		6, 7, 7, 8, 7, 8, 8, 8, 7, 8, 8, 8, 8, 8, 8, 8,
		7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		6, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8
	},
	{
		7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8
	},
	{
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8
	}
};

UInt64 ConstBitVector::select(UInt64 id) const
{
	TAIJU_ASSERT(id > 0);
	TAIJU_ASSERT(id <= num_zeros_);

	UInt64 block_id = select_block(id);
	id -= (block_id * NUM_BITS_PER_BLOCK) - (ranks_[block_id] >> 24);

	UInt64 unit_id = select_unit(id, block_id);
	id -= (unit_id * NUM_BITS_PER_UNIT)
		- (((ranks_[block_id] << 8) >> (unit_id * 8)) & 0xFF);

	UInt64 unit = objs_.units()[(block_id * NUM_UNITS_PER_BLOCK) + unit_id];
	UInt64 bytes = count_ones(~unit);

	UInt64 offset = 0;
	if (id <= ((bytes << 32) >> 56))
		offset += 32;
	if (id <= ((bytes << (offset + 16)) >> 56))
		offset += 16;
	if (id <= ((bytes << (offset + 8)) >> 56))
		offset += 8;
	id -= ((bytes << offset) << 8) >> 56;

	UInt64 bit_id = NUM_BITS_PER_UNIT - (offset + 8);
	bit_id += table_[id][(unit >> bit_id) & 0xFF];
	bit_id += block_id * NUM_BITS_PER_BLOCK + unit_id * NUM_BITS_PER_UNIT;

	return bit_id - 1;
}

UInt64 ConstBitVector::size() const
{
	return sizeof(UInt64) + objs_.size() + ranks_.size() + selects_.size();
}

void ConstBitVector::clear()
{
	num_zeros_ = 0;
	objs_.clear();
	ranks_.clear();
	selects_.clear();
}

void ConstBitVector::swap(ConstBitVector *target)
{
	std::swap(num_zeros_, target->num_zeros_);
	objs_.swap(&target->objs_);
	ranks_.swap(&target->ranks_);
	selects_.swap(&target->selects_);
}

const void *ConstBitVector::map(Mapper mapper)
{
	ConstBitVector temp;

	temp.num_zeros_ = *mapper.map<UInt64>();
	mapper = temp.objs_.map(mapper);
	mapper = temp.ranks_.map(mapper);
	mapper = temp.selects_.map(mapper);

	swap(&temp);

	return mapper.address();
}

void ConstBitVector::read(Reader reader)
{
	ConstBitVector temp;

	reader.read(&temp.num_zeros_);
	temp.objs_.read(reader);
	temp.ranks_.read(reader);
	temp.selects_.read(reader);

	swap(&temp);
}

void ConstBitVector::write(Writer writer) const
{
	writer.write(num_zeros_);
	objs_.write(writer);
	ranks_.write(writer);
	selects_.write(writer);
}

inline UInt64 ConstBitVector::select_block(UInt64 id) const
{
	UInt64 block_id = (id - 1) / NUM_BITS_PER_BLOCK;
	UInt64 left = selects_.empty() ? 0
		: static_cast<UInt64>(selects_[block_id]);
	UInt64 right = selects_.empty() ? ranks_.num_objs()
		: static_cast<UInt64>(selects_[block_id + 1]) + 1;

	while (left + 1 < right)
	{
		UInt64 middle = (left + right) / 2;
		if (id <= (middle * NUM_BITS_PER_BLOCK) - (ranks_[middle] >> 24))
			right = middle;
		else
			left = middle;
	}

	return left;
}

inline UInt64 ConstBitVector::select_unit(UInt64 id, UInt64 index_id) const
{
	UInt64 rank = ranks_[index_id];
	for (UInt64 unit_id = 1; unit_id < NUM_UNITS_PER_BLOCK; ++unit_id)
	{
		if (id <= (unit_id * NUM_BITS_PER_UNIT)
			- ((rank >> ((unit_id - 1) * 8)) & 0xFF))
			return unit_id - 1;
	}
	return NUM_UNITS_PER_BLOCK - 1;
}

}  // namespace taiju
